A typical data storage system includes a controller, an input/output (I/O) cache and a set of disk drives. The I/O cache temporarily stores data received from an external host for subsequent storage in the set of disk drives, as well as temporarily stores data read from the set of disk drives for subsequent transmission to an external host. In order to efficiently coordinate the use of space within the I/O cache, the controller manages descriptors which identify and describe the status of respective memory blocks (e.g., 512 byte segments) of the I/O cache.
Some conventional approaches to managing descriptors involve the use of a memory construct called a Least-Recently-Used (LRU) queue. In one conventional approach (hereinafter referred to as the single-queue approach), each descriptor (i) is an entry of an LRU queue, and (ii) resides at a location within the LRU queue based on when the memory block identified by that descriptor (i.e., by that LRU entry) was accessed (e.g., a lookup operation) relative to other the blocks identified by the other descriptors (i.e., by the other LRU entries). In particular, the descriptor at the tail (or beginning) of the LRU queue identifies the most recently accessed block of the I/O cache, the next descriptor identifies the next most recently accessed block, and so on. Accordingly, the descriptor at the head (or end) of the LRU queue identifies the least recently used block of the I/O cache.
During operation, the controller reuses descriptors from the head of the LRU queue in response to cache miss operations. In particular, when the controller needs to move non-cached data into the I/O cache due to a cache miss, the controller (i) moves the non-cached data into the memory block of the I/O cache identified by the descriptor at the head of the LRU queue (i.e., the least recently used block of the I/O cache), and (ii) moves the descriptor from the head to the tail of the LRU queue to indicate that the identified block is now the most recently used block of the I/O cache.
In response to a cache hit, the data already resides in a block of the I/O cache. Accordingly, the controller simply moves the descriptor identifying that block from its current location within the LRU queue (e.g., perhaps in the middle of the LRU queue) to the tail of the LRU queue to indicate that the identified block is now the most recently used block of the I/O cache.
Another conventional approach to managing descriptors uses multiple LRU queues. In this approach (hereinafter referred to as the multi-queue approach), each descriptor (i) identifies a memory block of the I/O cache, and (ii) includes a cache hit field which stores the absolute number of cache hits which have occurred on that block. A first LRU queue includes descriptors to I/O cache blocks having a minimal number of hits (e.g., one or two cache hits). Other queues include descriptors to I/O cache blocks having higher numbers of hits.
During operation, the controller responds to cache misses by (i) pulling descriptors from the head of the first LRU queue to identify the least recently used blocks of the I/O cache for caching new data, (ii) updating the contents of the cache hit fields of the descriptors and (iii) placing the descriptors at the tail of the first LRU queue. In response to cache hits on I/O cache blocks, the controller updates the contents of the cache hit fields of the descriptors identifying those blocks and moves those blocks to the tails of the LRU queues based on results of a queue priority function. Further details of how the multi-queue approach works will now be provided with reference to the following example.
Suppose that a particular multi-queue approach uses four LRU queues which are numbered xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, xe2x80x9c2xe2x80x9d and xe2x80x9c3xe2x80x9d to correspond to results of a queue priority function as will now be explained in further detail. In response to a cache miss operation, the controller (i) pulls a descriptor from the head of the first LRU queue, (ii) writes the non-cached data to the block identified by that descriptor, (iii) initializes the contents of a cache hit field of that descriptor to xe2x80x9c1xe2x80x9d, and (iv) pushes that descriptor onto the tail of the first LRU queue. Since that descriptor is no longer at the head of the first LRU queue, that descriptor no longer identifies the least recently used block of the I/O cache.
After the passage of time and/or the occurrence of other I/O cache operations, the location of that descriptor within the first LRU queue may shift (e.g., that descriptor may migrate to the middle of the first LRU queue due to other descriptors being added to the tail of the first LRU queue in response to caching operations). In response to a subsequent cache hit on the block identified by that descriptor, the controller (i) increments the contents of the cache hit field of that descriptor, (ii) performs a queue priority function on the incremented contents to provide a queue priority function result, and moves that descriptor to a new location based on the queue priority function result. For example, suppose that the contents of the cache hit field of that descriptor is still xe2x80x9c1xe2x80x9d and that the queue priority function is log2(xe2x80x9ccontents of the cache hit fieldxe2x80x9d). In response to a cache hit on the block identified by that descriptor, the controller increments the contents of the cache hit field from xe2x80x9c1xe2x80x9d to xe2x80x9c2xe2x80x9d (indicating that there has now been one additional cache hit that has occurred on the block identified by that descriptor), generates a queue priority function result (e.g., log2(1) is xe2x80x9c0xe2x80x9d), and moves the descriptor to a new location of the multiple queues (e.g., from the middle of the first LRU queue to the tail of the first LRU queue) based on the queue priority function result.
It should be understood that, over time, the contents of the cache hit fields of the descriptors can increase to the point in which the queue priority function results direct the controller to move the descriptors to the tails of LRU queues other than the first LRU queue. For instance, if the incremented contents of a descriptor equals two, the result of the queue priority function is xe2x80x9c1xe2x80x9d (e.g., log2(2) is xe2x80x9c1xe2x80x9d), and the controller moves that descriptor from the first LRU queue to the second LRU queue. Similarly, while a descriptor resides in the second LRU queue, if the number of cache hits reaches the next log2 barrier (i.e., four), the controller moves that descriptor from the second LRU queue to a third LRU queue, and so on. Accordingly, in the multi-queue approach, the controller is configured to promote descriptors from each LRU queue to an adjacent higher-level LRU queue based on increases in the number of hits on the block identified by that descriptor.
It should be understood that the controller is also configured to demote descriptors from each LRU queue to an adjacent lower-level LRU queue as the descriptors reach the heads of that LRU queue and a lifetime timer expires. For example, when a descriptor reaches the head of the third LRU queue, the controller demotes that descriptor to the tail of the next lowest LRU queue, i.e., the tail of the second LRU queue. Similarly, when a descriptor reaches the head of the second LRU queue, the controller demotes that descriptor to the tail of the first LRU queue. Finally, as mentioned earlier, the controller reuses the descriptors at the head of the first LRU queue, which identify the least recently used blocks of the I/O cache, in response to cache misses.
In both the single-queue and multi-queue approaches, the descriptors within the LRU queues are typically arranged as doubly-linked lists. That is, each descriptor includes a forward pointer which points to the adjacent preceding descriptor in an LRU queue, and a reverse pointer which points to the adjacent succeeding descriptor in the LRU queue. When the controller moves a descriptor from the middle of an LRU queue to the tail of the same LRU queue or a new LRU queue, the controller performs multiple linked list operations. These linked list operations will now be described in further detail.
Suppose that the controller must move a particular descriptor from the middle of an LRU queue to the tail of the LRU queue (e.g., in response to a cache hit operation). First, the controller identifies the adjacent preceding descriptor and the adjacent succeeding descriptor by reading forward and reverse pointers of the particular descriptor. Second, the controller removes the particular descriptor from the LRU queue by (i) reading, modifying and storing the forward pointer of the adjacent preceding descriptor and (ii) reading, modifying and storing the reverse pointer of the adjacent succeeding descriptor. Third, the controller finds the first or tail descriptor in the LRU queue by reading a tail pointer of the LRU queue. Next, the controller adds the particular descriptor to the tail of the LRU queue by reading, modifying and storing the reverse pointer of first descriptor, and modifying and storing the forward and reverse pointers of the particular descriptor (the reverse pointer of the particular descriptor can be set to NULL or set to point to the particular descriptor itself since it is now the tail entry). Finally, the controller indicates that the particular descriptor is now at the tail of the LRU queue for a subsequent LRU access operation by modifying the tail pointer of the LRU queue.
Unfortunately, there are deficiencies to the above-described conventional approaches to managing descriptors using LRU queues. For example, in the both of the above-described conventional single-queue and multi-queue approaches, a substantial number of linked list operations are required when moving a descriptor from the middle of an LRU queue to a new location. For instance, when a controller of a data storage system moves a descriptor from the middle of an LRU queue to the tail of the LRU queue, there can be as many as 10 operations. In particular, there is usually one operation for reading the forward and reverse pointers of the particular descriptor to be moved in order to identify the adjacent preceding and adjacent succeeding descriptors, two operations for reading the adjacent preceding descriptor and setting its forward pointer to point to the adjacent succeeding descriptor, two operations for reading the adjacent succeeding descriptor and setting its reverse pointer to point to the adjacent preceding descriptor, one operation for reading the tail pointer to find the tail of the LRU queue, two operations for reading the old tail descriptor and setting the reverse pointer of the old tail descriptor to point to the particular descriptor, one operation for setting the forward and reverse pointers of the particular descriptor (the forward pointer pointing to the old tail descriptor, and the reverse pointer set to NULL or pointed to the particular descriptor itself), and one operation for setting the tail pointer to point to the particular descriptor.
While the controller of the data storage system moves the descriptor from the middle to the tail of the LRU queue, the controller typically locks the entire LRU queue to prevent another process from modifying the LRU queue (and perhaps corrupting the operation of the controller) until the controller is done. Accordingly, such operations can block other processes in the critical path from executing and pose a resource bottleneck to the data storage system. As a result, data storage systems which use the above-described conventional approaches are susceptible to performance drawbacks when placed in situations requiring large amounts of LRU queue modification.
In contrast to the above-described conventional approaches to managing descriptors using LRU queues, the invention is directed to techniques for managing descriptors which involve the moving descriptors from the heads of multiple queues based on access frequency and expiration timers. Such operation provides approximate LRU functionality while (i) alleviating the need for moving descriptors from the middles of LRU queues, and (ii) avoiding the above-described resource bottlenecking deficiencies (e.g., the high number of operations) associated with moving descriptors from the middle of LRU queues.
One embodiment of the invention is directed to a device (e.g., a control module for a data storage system, a secondary cache device, a general purpose computer, etc.) for managing descriptors which correspond to storage locations (e.g., cache blocks). The device includes memory and a control circuit coupled to the memory. The control circuit is configured to arrange the descriptors, which correspond to the storage locations, into multiple queues within the memory based on storage location access frequencies (e.g., based on results of a queue priority function). The control circuit is further configured to determine whether an expiration timer for the particular descriptor has expired in response to a particular descriptor reaching a head of a particular queue. The control circuit is further configured to move the particular descriptor from the head of the particular queue to a different part of the multiple queues, wherein the different part is identified based on access frequency when the expiration timer for the particular descriptor has not expired (e.g., to the tail of queue based on a queue priority function), and not based on access frequency when the expiration timer for the particular descriptor has expired (e.g., automatically to the tail of the adjacent lower level queue).
With this operation, the storage locations corresponding to the descriptors nearer the heads of the queues tend to be less recently used than the storage locations corresponding to the descriptors nearer the tails of the queues thus approximating the functionality of conventional descriptor management approaches which use LRU queues. However, by removing descriptors from the heads of the queues, the device alleviates the need to remove descriptors from middles of the queues thus avoiding the associated high number of linked list operations which characterize conventional approaches that remove descriptors from the middles of LRU queues. Rather, less operations are performed when simply moving descriptors from the heads of queues expire to the tails of queues (e.g., to the tail of the adjacent lower queue when the expiration timers of the descriptors have expired, and to a tail of a queue based on a queue priority function when the expiration timers of the descriptors have not expired) to achieve approximate LRU functionality. Moreover, experimental studies have shown that the performance of the invention techniques provide similar effectiveness in optimizing cache use (e.g., to avoid cache misses) but at significantly less overhead.